package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 二叉搜索树与双向链表
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：524547
 * 本题知识点： 分治
 *  算法知识视频讲解
 * 题目描述
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * 说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
 */
public class ConvertDoubleLinkedList {

    @Test
    public void test(){
        System.out.println(Convert(null));
    }

    //思路:用中序遍历将节点按顺序装入,然后修改节点的左右指针(这个过程并没有产生新节点哦).
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return pRootOfTree;
        }

        ArrayList<TreeNode> inorder = new ArrayList<>();
        inorder(inorder,pRootOfTree);

        for (int i = 0; i < inorder.size(); i++) {
            if (i != 0) {
                inorder.get(i).left = inorder.get(i-1);
            }
            if (i!=inorder.size()-1){
                inorder.get(i).right = inorder.get(i+1);
            }
        }

        return inorder.get(0);
    }

    private void inorder(ArrayList<TreeNode> inorder, TreeNode treeNode) {
        if (treeNode.left != null) {
            inorder(inorder,treeNode.left);
        }

        inorder.add(treeNode);

        if (treeNode.right!=null) {
            inorder(inorder, treeNode.right);
        }
    }
}
